use crate::utils::access_guard::AccessGuard;
use std::cell::Cell;
use std::fmt::{Debug, Formatter};
use std::mem;
use std::ptr::NonNull;
#[repr(transparent)]
pub(crate) struct SingleLinkedList<T>
where
    T: SingleLinkedNode<T>,
{
    pub(super) head: Cell<Option<NonNull<T>>>,
}

impl<T> Debug for SingleLinkedList<T>
where
    T: SingleLinkedNode<T>,
{
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        f.write_fmt(format_args!(
            "SingleLinkedList(head: {:?})",
            self.head.get()
        ))
    }
}

pub(crate) trait SingleLinkedNode<T> {
    fn next(&mut self) -> &mut Option<NonNull<T>>;
}

impl<T> Default for SingleLinkedList<T>
where
    T: SingleLinkedNode<T>,
{
    fn default() -> Self {
        Self {
            head: Cell::new(None),
        }
    }
}

impl<T> SingleLinkedList<T>
where
    T: SingleLinkedNode<T>,
{
    pub(crate) fn is_empty(&self) -> bool {
        self.head.get().is_none()
    }
    pub(crate) fn push<G, N>(&self, access_guard: &G, node: N)
    where
        G: AccessGuard<T>,
        N: Into<NonNull<T>>,
    {
        let node = access_guard.access(node);
        let node_next_ptr = node.next();
        debug_assert!(node_next_ptr.is_none());
        *node_next_ptr = self.head.get();
        self.head.set(Some(NonNull::from(node)));
    }
    pub(crate) fn pop<G>(&self, access_guard: &G) -> Option<NonNull<T>>
    where
        G: AccessGuard<T>,
    {
        match self.head.get() {
            None => None,
            Some(head) => {
                let next = access_guard.access(head).next().take();
                self.head.set(next);
                Some(head)
            }
        }
    }

    pub(crate) fn iter<'r, G>(
        &self,
        access_guard: &'r G,
    ) -> impl Iterator<Item = NonNull<T>> + use<'r, G, T>
    where
        G: AccessGuard<T>,
    {
        ListIterator {
            current: self.head.get(),
            access_guard,
        }
    }
}

struct ListIterator<'r, T, G>
where
    G: AccessGuard<T>,
    T: SingleLinkedNode<T>,
{
    current: Option<NonNull<T>>,
    access_guard: &'r G,
}

impl<'r, T, G> Iterator for ListIterator<'r, T, G>
where
    G: AccessGuard<T>,
    T: SingleLinkedNode<T>,
{
    type Item = NonNull<T>;

    fn next(&mut self) -> Option<Self::Item> {
        match self.current {
            Some(current) => {
                let current_node = self.access_guard.access(current);
                mem::replace(&mut self.current, *current_node.next())
            }
            None => None,
        }
    }
}

#[cfg(test)]
mod tests {
    use crate::utils::access_guard::AccessGuard;
    use crate::utils::single_linked_list::{SingleLinkedList, SingleLinkedNode};
    use std::iter;
    use std::ptr::NonNull;

    struct TestNode {
        next: Option<NonNull<TestNode>>,
    }

    impl SingleLinkedNode<TestNode> for TestNode {
        fn next(&mut self) -> &mut Option<NonNull<TestNode>> {
            &mut self.next
        }
    }

    struct TestAccessGuard;

    impl AccessGuard<TestNode> for TestAccessGuard {
        fn before_access(&self, _ptr: NonNull<TestNode>) {}
    }

    fn assert_list<T, G>(guard: &G, list: &SingleLinkedList<T>, nodes: &Vec<T>, expected: &[usize])
    where
        G: AccessGuard<T>,
        T: SingleLinkedNode<T>,
    {
        let mut node_idx = 0;
        let mut current = list.head.get();
        while let Some(node_ptr) = current {
            let node = guard.access(node_ptr);
            assert_eq!(node_ptr, NonNull::from(&nodes[expected[node_idx]]));
            node_idx += 1;
            current = *node.next();
        }
        assert_eq!(node_idx, expected.len());

        // test iter
        let iter_count = list
            .iter(guard)
            .enumerate()
            .map(|(idx, node_ptr)| {
                assert_eq!(node_ptr, NonNull::from(&nodes[expected[idx]]));
            })
            .count();
        assert_eq!(iter_count, expected.len());
        assert_eq!(expected.is_empty(), list.head.get().is_none())
    }
    #[test]
    fn test_single_linked_list() {
        let guard = TestAccessGuard;
        let nodes = iter::repeat(0)
            .take(5)
            .map(|_| TestNode { next: None })
            .collect::<Vec<_>>();

        // Test empty list
        let list = SingleLinkedList::default();
        assert_list(&guard, &list, &nodes, &[]);
        assert!(list.is_empty());
        assert!(list.pop(&guard).is_none());

        // Push and pop nodes
        list.push(&guard, &nodes[0]);
        assert_list(&guard, &list, &nodes, &[0]);
        let node = list.pop(&guard).unwrap();
        assert_list(&guard, &list, &nodes, &[]);
        assert_eq!(node, NonNull::from(&nodes[0]));
        assert!(nodes[0].next.is_none());

        // Push many nodes
        nodes.iter().for_each(|node| {
            let old_head = list.head.get();
            list.push(&guard, node);
            assert_eq!(list.head.get().unwrap(), NonNull::from(node));
            assert_eq!(old_head, node.next);
        });
        assert_list(&guard, &list, &nodes, &[4, 3, 2, 1, 0]);
    }
}
